import java.util.HashMap;
import java.util.Map;

/**
 * 290. 单词规律
 * https://leetcode-cn.com/problems/word-pattern/
 */
public class Solutions_290 {
    public static void main(String[] args) {
        String pattern = "abba", str = "dog cat cat dog";  // output: true
//        String pattern = "abba", str = "dog cat cat fish";  // output: false
//        String pattern = "aaaa", str = "dog cat cat dog";  // output: false
//        String pattern = "abba", str = "dog dog dog dog";  // output: false

        boolean result = wordPattern(pattern, str);
        System.out.println(result);
    }

    public static boolean wordPattern(String pattern, String s) {
        if (pattern == null && s == null) {
            return true;
        }
        if (pattern == null || s == null) {
            return false;
        }
        String[] ss = s.split(" ");
        if (ss.length != pattern.length()) {
            return false;
        }
        // visited[2] = true，表示 pattern 中字符 'b' 已经匹配过单词
        boolean[] visited = new boolean[26];
        Map<String, Character> map = new HashMap<>();
        char[] arr = pattern.toCharArray();

        for (int i = 0; i < ss.length; i++) {
            if (map.containsKey(ss[i])) {
                // 本次匹配的字符，与之前匹配的字符不同时，无法匹配
                if (map.get(ss[i]) != arr[i]) {
                    return false;
                }
            } else {
                if (visited[arr[i] - 'a']) {
                    // arr[i] 被其他单词匹配过了，那么 ss[i] 单词是无法匹配的
                    return false;
                }
                // 首次匹配成功，记录到 map 中
                visited[arr[i] - 'a'] = true;
                map.put(ss[i], arr[i]);
            }
        }
        return true;
    }
}
